%****************************************************************************%
%* DIET User's Manual plugin scheduler chapter file                         *%
%*                                                                          *%
%*  Author(s):                                                              *%
%*    - Alan SU (Alan.SU@ens-lyon.fr)                                       *%
%*                                                                          *%
%* $LICENSE$                                                                *%
%****************************************************************************%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% \documentclass{article}

\newenvironment{code}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\bfseries\tt}
{\end{list}}

\newenvironment{tinycode}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\tiny\bfseries\tt}
{\end{list}}

%% \begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Scheduling in DIET}
\label{ch:plugin}

\section{Introduction}

We introduce a \emph{plugin scheduling} facility, designed to allow
\diet service developers to define application-specific performance
measures and to implement corresponding scheduling strategies.  This
section describes the default scheduling policy in \diet and the
interface to the plugin scheduling facility.

\section{Default Scheduling Strategy}\label{sect:default_sched}

The \diet scheduling subsystem is based on the notion that, for the
sake of system efficacy and scalability, the work of determining the
appropriate schedule for a parallel workload should be distributed
across the computational platform.  When a task in such a parallel
workload is submitted to the system for processing, each Server Daemon
(\sed) provides a \emph{performance estimate}~-- a collection of data
pertaining to the capabilities of a particular server in the context
of a particular client request~-- for that task.  These estimates are
passed to the server's parent agent; agents then sort these responses
in a manner that optimizes certain performance criteria.  Effectively,
candidate {\sed}s are identified through a distributed scheduling
algorithm based on pairwise comparisons between these performance
estimations; upon receiving server responses from its children, each
agent performs a local scheduling operation called \emph{server
response aggregation}.  The end result of the agent's aggregation
phase is a list of server responses (from servers in the subtree
rooted at said agent), sorted according to the aggregation method in
effect.  By default, the aggregation phase implements the following
ordered sequence of tests:

\begin{enumerate}
\item \textbf{FAST/NWS data}: {\sed}s compiled and properly configured
  with FAST~\cite{Qui02} and NWS~\cite{WSH99} are capable of making
  dynamic performance estimates.  If such data were generated by the
  {\sed}s, these are the metrics on which agents select servers.
\item \textbf{Round-robin}: In the absence of application- and
  platform-specific performance data, the \diet scheduler attempts to
  probabilistically achieve load balance by assigning client requests
  on a round-robin basis.  Essentially each server records a timestamp
  indicating the last time at which it was assigned a job for
  execution.  Each time a request is received, the \sed computes the
  time elapsed since its last execution, and among the responses it
  receives, \diet agents select {\sed}s with a longer elapsed time.
\item \textbf{Random}: If the {\sed} is unable to store timestamps, the
  \diet scheduler will chose randomly when comparing two otherwise
  equivalent {\sed} performance estimations.
\end{enumerate}

\textbf{Warning:} If DIET is compiled with option \texttt{DIET\_USE\_CORI},
FAST/NWS Scheduling is deactivated (See
Chapter~\ref{chapter:performance} for more information about CoRI).

In principle, this scheduling policy prioritizes servers that are able
to provide useful performance prediction information (as provided by
the FAST and NWS facilities).  In general, this approach works well
when all servers in a given DIET hierarchy are capable of making such
estimations.  However, in platforms composed of {\sed}s with varying
capabilities, load imbalances may occur: since DIET systematically
prioritizes server responses containing FAST and/or NWS data, servers
that do not respond with such performance data will never be
chosen.

We have designed a plugin scheduler facility to
enable the application developer to tailor the DIET scheduling to the
targeted application.
This functionality provides
the application developer the means to extend the notion of a
performance estimation to include metrics that are
application-specific, and to instruct DIET how to treat those data in
the aggregation phase.
We describe these interfaces in the following sections.


\section{Plugin Scheduler Interface}

Distributed applications are varied and often exhibit performance
behavior specific to the domain from which they arise.  Consequently,
application-specific scheduling approaches are often necessary to
achieve high-performance execution.  We propose an extensible
framework to build
\emph{plugin schedulers}, enabling application developers to specify
performance estimation metrics that are tailored to their individual
needs.

%% This section introduces the principal components of the basic plugin
%% scheduler framework.

\subsection{Estimation Metric Vector}\label{sect:estvector}

The new type \texttt{estVector\_t} represents an
\emph{estimation vector}, logically a structure that can manage a
dynamic collection of performance estimation values.  It contains
values that represent the performance profile provided by a
{\sed} in response to a DIET service request.  This collection of values
may include either standard performance measures that are available
through DIET, or developer-defined values that are meaningful solely in
the context of the application being developed.

\subsection{Standard Estimation Tags}\label{sect:estTags}

To access to the different fields of the \texttt{estVector\_t}, it is
necessary to specify the tag that correspond to a specific information
type.  Table~\ref{t:tags} describes this correspondence.  Some tags
represent a list of values, one has to use the
\texttt{diet\_est\_array\_*}  functions to have access to them. In
Table~\ref{t:tags},  the second column marks these multi-value tags.

The tag \textit{ALLINFOS} is a special: his field is 
always empty, but it allows to fill the vector with all known tags 
by the particular collector.
 
\begin{table}[h]
 \tiny
 \centering
 \begin{tabular}[c]{|c|c|c|}\hline
%FAST ligne

  \texttt{Information tag}  &multi-& \texttt{Explication} \\[5pt]
 \texttt{starts with EST\_} &value& \\[5pt]
  \hline

%TAGS lines
 \textit{TCOMP        }&& the predicted time 
                       to solve a problem \\[5pt]
  \hline
  \textit{TIMESINCELASTSOLVE} &   & time since last solve has been made (sec) \\[5pt]
  \hline
  \textit{FREECPU      }&& amount of free CPU power between 0 and 1 \\[5pt]
  \hline
  \textit{FREEMEM      }&& amount of free  memory (Mb) \\[5pt]
  \hline
  \textit{NBCPU        }&& number of available processors  \\[5pt]
  \hline
  \textit{CPUSPEED     }&x& frequency of CPUs (MHz) \\[5pt]
  \hline
  \textit{TOTALMEM     }&& total memory size (Mb)  \\[5pt]
  \hline
  \textit{AVGFREECPU   }&& average amount of free CPU power in [0..1] \\[5pt]
  \hline
  \textit{BOGOMIPS     }&x& CPUs' bogomips \\[5pt]
  \hline
  \textit{CACHECPU     }&x& cache size CPUs (Kb) \\[5pt]
  \hline
  \textit{TOTALSIZEDISK}&& size of the partition (Mb)\\[5pt]
  \hline
  \textit{FREESIZEDISK }&& amount of free place on partition (Mb)\\[5pt]
  \hline
  \textit{DISKACCESREAD}&& average time to read on disk (Mb/sec) \\[5pt]
  \hline
  \textit{DISKACCESWRITE}&& average time to write to disk (sec) \\[5pt]
  \hline
  \textit{ALLINFOS     }&x& [empty] fill all possible fields \\[5pt]
  \hline
  \textit{PARAL\_NB\_FREE\_RESOURCES\_IN\_DEFAULT\_QUEUE} & & number
  of idle resources \\[5pt] 
  \hline
 \end{tabular}
 \caption{Explication of the estimation tags}
 \label{t:tags}
\end{table}

\subsubsection{Standard Performance Metrics}

To access to the existing default performance estimation
routines (as described in Chapter~\ref{chapter:performance}), the following
functions are available to facilitate the construction of custom
performance estimation functions:
\begin{itemize}
\item FAST- and NWS-based performance estimation metrics can be used in the plugin scheduler. 
  See the Section~\ref{subsection:callFAST} for information on how to use them.
\item The time elapsed since the last execution (to enable
  the round-robin scheduler) is stored in an estimation metric vector
  by calling
  \begin{tabbing}
    \texttt{int diet\_estimate\_lastexec(}\=\texttt{estVector\_t ev,} \\
    \> \texttt{const diet\_profile\_t* const profilePtr)};
  \end{tabbing}
  with an appropriate value for \texttt{ev} and the
  \texttt{profilePtr} corresponding to the current DIET request.
\item The number of waiting jobs when using the maximum concurrent jobs
  limit is stored in an estimation metric vector by calling
  \begin{tabbing}
    \texttt{int diet\_estimate\_waiting\_jobs(}\=\texttt{estVector\_t ev)};
  \end{tabbing}
\item CoRI allows to access in an easy way to basic performance 
prediction. See Chapter~\ref{sec:CORI} to know more about the use of it.

\end{itemize}

In the future, we plan to expand the suite of default estimation
metrics to include dynamic internal \diet system state information
(\eg queue lengths).

\subsubsection{Developer-defined Performance Metrics}

Application developers may also define performance values to be
included in a \sed response to a client request.  For example, a \diet
\sed that provides a service to query particular databases may need to
include information about which databases are currently resident in
its disk cache, in order that an appropriate server be identified for
each client request.  To store such values, the \sed developer should
first choose a unique integer identifier, referred to as the
\emph{tag} to denote each logical datum to be stored.  Values are
associated with tags using the following interface:
\begin{code}
int diet\_est\_set(estVector\_t ev, int userTag, double value);
\end{code}
The \texttt{ev} parameter is the estimation vector where the
value will be stored, the \texttt{userTag} parameter denotes the
chosen tag, and \texttt{value} indicates the value to be associated
with the tag.  Tagged data are used to effect
scheduling policies by defining custom server response
aggregation methods, described in Section~\ref{sect:agg_methods}.

\subsection{Estimation Function}\label{sect:est_fn}

The default behavior of a {\sed} when a service request arrives from
its parent agent is to store the following information in the
request profile:
\begin{enumerate}
\item \textbf{FAST-based execution time predictions}: DIET {\sed}s
  attempt to call FAST
  routines to obtain execution time predictions based on the type of
  service requested, if FAST was available at compilation time.  If
  available, such predictions are stored in the
  performance estimate.
\item \textbf{NWS-based dynamic resource information}: If NWS library
  functions are available, performance estimates may include dynamic
  resource performance information about CPU availability, free
  memory, and network bandwidth.
\item \textbf{Elapsed time since last execution}: To implement the
  default round-robin behavior in absence of FAST and NWS facilities,
  each {\sed} stores a timestamp of its last execution.  When a service
  request arrives, the difference between that timestamp and the
  current time is added to the performance estimate.
\end{enumerate}
This is accomplished by using the \texttt{diet\_estimate\_fast} and
\texttt{diet\_estimate\_lastexec} functions described in
Section~\ref{sect:estvector}.

To implement a plugin scheduler, we define an
interface that admits customizable performance estimation routines:
\begin{tabbing}
  \texttt{typedef void (* diet\_perfmetric\_t)(}
    \=\texttt{diet\_profile\_t*,} \\
    \>\texttt{estVector\_t);} \\
\end{tabbing}
\begin{tabbing}
  \texttt{diet\_perfmetric\_t} \\
  \texttt{diet\_service\_use\_perfmetric(diet\_perfmetric\_t perfmetric\_fn);}\\
\end{tabbing}
%% \begin{code}
%%   diet\_perfmetric\_t\\
%%   diet\_service\_use\_perfmetric(diet\_perfmetric\_t perfmetric\_fn);\\
%% \end{code}
Thus, the type \texttt{diet\_perfmetric\_t} is a function pointer that
takes as arguments a performance estimation (represented by the
\texttt{estVector\_t} object) and a DIET service request
profile.  The application
developer can associate such a function, or
\emph{performance estimation routine}, with DIET services via the
\texttt{diet\_service\_use\_perfmetric} interface.  This interface
returns the previously registered performance estimation routine, if
one was defined (and
\texttt{NULL} otherwise).  At this point, a service added using the
\texttt{diet\_service\_table\_add} function will be associated with
the declared performance estimation routine.
Additionally, a performance estimation routine so specified will be
associated with \emph{all} services added into the service table until
another call to the
\texttt{diet\_service\_use\_perfmetric} interface is made.
In the performance estimation routine, the {\sed} developer should store
in the provided estimation vector
any performance data used in the server response aggregation
methods (described in the next section).

\subsection{Aggregation Methods}\label{sect:agg_methods}

At the time a DIET service is defined, an \emph{aggregation method}~--
the logical mechanism by which {\sed} responses are sorted~-- is
associated with the service; the default behavior was described in
Section~\ref{sect:default_sched}.

If application-specific data \emph{are} supplied (i.e.,~the
estimation function has been redefined), an alternative method for
aggregation is needed.  Currently, a basic
\emph{priority scheduler} has been implemented, enabling an
application developer to specify a series of performance values that
are to be optimized in succession.  A developer may implement a
priority scheduler using the following interface:
\begin{code}
\begin{tabbing}
diet\_aggregator\_desc\_t* \\
diet\_profile\_desc\_aggregator(diet\_profile\_desc\_t* profile); \\
\\
int diet\_aggregator\_set\_type(\=diet\_aggregator\_desc\_t* agg, \\
\> diet\_aggregator\_type\_t atype); \\
\\
int diet\_aggregator\_priority\_max(\=diet\_aggregator\_desc\_t* agg, \\
\> diet\_est\_tag\_t tag); \\
\\
int diet\_aggregator\_priority\_min(\=diet\_aggregator\_desc\_t* agg, \\
\> diet\_est\_tag\_t tag); \\
\\
int diet\_aggregator\_priority\_maxuser(\=diet\_aggregator\_desc\_t* agg, \\
\> int val); \\
\\
int diet\_aggregator\_priority\_minuser(\=diet\_aggregator\_desc\_t* agg, \\
\> int val); \\
\end{tabbing}
\end{code}
The \texttt{diet\_profile\_desc\_aggregator} and
\texttt{diet\_aggregator\_set\_type} functions fetch and configure the
aggregator corresponding to a DIET service profile, respectively.
In particular, a priority scheduler is declared by invoking the latter
function with \texttt{DIET\_AGG\_PRIORITY} as the \texttt{agg}
parameter.
Recall that from the point of view of an agent, the aggregation phase
is essentially a sorting of the server responses from its children.
A priority scheduler logically uses a series of user-specified tags to
perform the pairwise server comparisons needed to construct the
sorted list of server responses.

To define the tags and the order in which they should be compared,
four functions are introduced.  These functions, of the form
\texttt{diet\_aggregator\_priority\_*}, serve to identify the
estimation values to be optimized during the aggregation phase.  The
\texttt{\_min} and \texttt{\_max} forms indicate that a standard
performance metric (e.g.,~time elapsed since last execution, from the
\texttt{diet\_estimate\_lastexec} function) is to be either
minimized or maximized, respectively.  Similarly, the
\texttt{\_minuser} and \texttt{\_maxuser} forms indicate the analogous
operations on user-supplied estimation values.  Calls to these
functions indicate the order of \textbf{precedence} of the tags.

Each time two server responses need to be compared, the values
associated with the tags specified in the priority aggregator are
retrieved.  In the specified order, pairs of corresponding values are
successively compared, passing to the next tag only if the values for
the current tag are identical.  If one server response contains a
value for the metric currently being compared, and another does not,
the response with a valid value will be selected.  If at any point
during the treatment of tags \emph{both} responses lack the necessary
tag, the comparison is declared indeterminate.
This process continues until one response is
declared superior to the other, or all tags in the priority aggregator
are exhausted (and the responses are judged equivalent).


\section{Example}

A new example has been added to the DIET distribution to illustrate
the usage of the plugin scheduler functionality; this code is
available in the directory
\begin{code}
src/examples/plugin\_example/
\end{code}
A DIET server and client corresponding to a simulation of a
database research application are provided.  If the construction of
examples was enabled during DIET configuration, two binaries
\texttt{server} and \texttt{client} will be built in this directory.
Having deployed a DIET agent hierarchy, the server may be
instantiated:
\begin{code}
  \$ server <SeD\_config> <DB> [ <DB> ... ]
\end{code}
where \texttt{<DB>} are string(s) that represent the existence of
a particular database at the {\sed}'s site.  A client would pose a query
against a set of databases:
\begin{code}
  \$ client <client\_config> <DB> [ <DB> ... ]
\end{code}
The application uses the plugin scheduling facility to prioritize the
existence of databases in selecting a server, and thus, the expected
result is that one of the {\sed}s with the fewest number of database
mismatches will be selected.

In the \texttt{main} function of the \texttt{server.c} file, the
following block of code (a)~specifies the use of the priority
aggregator for this service, (b)~declares a performance estimation
function to supply the necessary data at request-time, and
(c)~defines the order of precedence of the performance values
(i.e.,~minimizing the number of database mismatches, and then
maximizing the elapsed execution time).
\begin{verbatim}
  {
    /* new section of the profile: aggregator */
    diet_aggregator_desc_t *agg;
    agg = diet_profile_desc_aggregator(profile);

    /* for this service, use a priority scheduler */
    diet_aggregator_set_type(agg, DIET_AGG_PRIORITY);          /* (a) */

    /* install our custom performance function */
    diet_service_use_perfmetric(performanceFn);                /* (b) */

    /* define the precedence order */
    diet_aggregator_priority_minuser(agg, 0);                  /* (c) */
    diet_aggregator_priority_max(agg, EST_TIMESINCELASTSOLVE); /* (c) */
  }
\end{verbatim}
The performance function \texttt{performanceFn} is defined as follows:
\begin{verbatim}
static void performanceFn(diet_profile_t* pb, estVector_t perfValues);

[...]

/*
** performanceFn: the performance function to use in the DIET
**   plugin scheduling facility
*/
static void
performanceFn(diet_profile_t* pb, estVector_t perfValues)
{
  const char *target;
  int numMismatch;

  /* string value must be fetched from description; value is NULL */
  target = (diet_paramstring_get_desc(diet_parameter(pb, 0)))->param;
  numMismatch = computeMismatches(target);

  /*
  ** store the mismatch value in the user estimate space,
  ** using tag value 0
  */
  diet_est_set(perfValues, 0, numMismatch);

  /* also store the timestamp since last execution */
  diet_estimate_lastexec(perfValues, pb);
}
\end{verbatim}
The function \texttt{computeMismatches} (defined earlier in
\texttt{server.c}) calculates the number of requested databases that
are not present on the {\sed} making the evaluation.
Together, these two code segments serve to customize the generation of
performance information and the treatment of these data in the context
of the simulated database search.
Finally, it should be noted that the existence of a plugin scheduler
is completely transparent to the client, and thus client code need not
be changed.

%
% Scheduling at agents level
%
\input{agent_scheduler.tex}

\section{Future Work}

We have two primary efforts planned for extensions to the plugin
scheduler.
\begin{itemize}
\item \textbf{Additional information services}: We plan to add
  functionalities to enable the application developer to access and use
  data concerning the internal state of the DIET server (e.g.,~the
  current length of request queues).  As other performance measurement
  and evaluation tools are developed both within and external to the
  DIET project (see Chapter~\ref{chapter:performance}), some
  tools are already available to enable such 
  information to be incorporated
  in the context of the plugin scheduler.
\item \textbf{Enhanced aggregation methods}: The plugin scheduler
  implemented in the current release enables the DIET system to
  account for user-defined factors in the server selection process.
  However, the priority aggregation method is fairly rudimentary and
  lacks the power to express many imaginable comparison mechanisms.
  We plan to investigate methods to embed code into DIET agents
  (e.g.,~a simple expression interpreter) in a manner that is secure
  and that preserves performance.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% \end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

